package com.leetcode.No0813;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @program: Solution
 * @description: 最大平均值和的分组
 * @author: Wang Zhihua
 * @date: 2022-11-28
 */
public class Solution {

    double result;
    int[] nums;

    public double largestSumOfAverages(int[] nums, int k) {
        int len = nums.length;
        this.result = 0.0;
        this.nums = nums;
        dfs(0, len, k, 0L, 1L);
        return result;
    }

    // 范围 [left, right)
    public void dfs(int left, int right, int remainK, long totalSon, long totalMather) {
        if (remainK == 0) {
            if (left == right) {
                result = Math.max(result, 1.0 * totalSon / totalMather);
            }
            return;
        }
        for (int i = 1; left + i <= right - remainK; ++i) {
            long tmpSon = 0;
            for (int j = left; j < left + i; ++j) {
                tmpSon += nums[j];
            }
            dfs(left + i, right, remainK - 1, totalSon * i + totalMather * tmpSon, i * totalMather);
        }
    }

    @Test
    public void test01() {
        int[] nums;
        int k;

//        nums = new int[]{9,1,2,3,9};
//        k = 3;
//        System.out.println(new Solution().largestSumOfAverages(nums, k));
//
//        nums = new int[]{1,2,3,4,5,6,7};
//        k = 4;
//        System.out.println(new Solution().largestSumOfAverages(nums, k));

        nums = new int[]{4663,3020,7789,1627,9668,1356,4207,1133,8765,4649,205,6455,8864,3554,3916,5925,3995,4540,3487,5444,8259,8802,6777,7306,989,4958,2921,8155,4922,2469,6923,776,9777,1796,708,786,3158,7369,8715,2136,2510,3739,6411,7996,6211,8282,4805,236,1489,7698};
        k = 27;
        System.out.println(new Solution().largestSumOfAverages(nums, k));
    }
}
